#分治法求解
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# lists = [[1,4,5],[1,3,4],[2,6]]
list1=ListNode(1)
list1.next=ListNode(4)
list1.next.next=ListNode(5)
list2=ListNode(1)
list2.next=ListNode(3)
list2.next.next=ListNode(4)
list3=ListNode(2)
list3.next=ListNode(6)
lists=[list1,list2,list3]
#使用分治排序里面的合并步骤来求解
def merge(list1,list2):
    if list1==None and list2==None:
        return None
    if list1!=None and list2==None:
        return list1
    if list1==None and list2!=None:
        return list2
    if list1!=None and list2!=None:
        # print("-------------------进行合并：----------------------")
        # print("list1-----------------------------------------")
        # ls1=list1
        # while ls1!=None:
        #     print(ls1.val,end=" ")
        #     ls1=ls1.next
        # print()
        # ls2=list2
        # print("list2========================================")
        # while ls2!=None:
        #     print(ls2.val,end=" ")
        #     ls2=ls2.next
        # print()
        newList=ListNode()
        if list1.val<=list2.val:
            newList.val=list1.val
            list1=list1.next
        else:
            newList.val=list2.val
            list2=list2.next
        pre=newList
        while list1!=None and list2!=None:
            pre.next=ListNode()
            if list1.val <= list2.val:
                pre.next.val = list1.val
                list1 = list1.next
            else:
                pre.next.val = list2.val
                list2 = list2.next
            pre=pre.next
        while list1!=None:
            pre.next=ListNode()
            pre.next.val = list1.val
            list1 = list1.next
            pre=pre.next
        while list2!=None:
            pre.next=ListNode()
            pre.next.val=list2.val
            list2=list2.next
            pre=pre.next
        print("合并之后的结果——————————————————————————")
        newList1=newList
        while newList1!=None:
            print(newList1.val,end=" ")
            newList1=newList1.next
        print()
        print("****************************************************")
        return newList
def divideAndMerge(lists):
    # print(len(lists))
    #出口条件
    if len(lists)==1:
        return lists[0]
    if len(lists)==0:
        return None
    midIndex=int(len(lists)/2)
    #分
    d1=divideAndMerge(lists[0:midIndex])
    d2=divideAndMerge(lists[midIndex:])
    #合
    return merge(d1,d2)

def mergeKLists(lists):
    list=divideAndMerge(lists)
    while list!=None:
        print(list.val)
        list=list.next

print(mergeKLists(lists))